// -*-c++-*-

// Cassie Chin (cassiechin9793@gmail.com)

// These structures are containers to organize the required steps of the AETG algorithm
// Test -> Candidate -> TestSuite -> Result
// A Candidate structure contains a number of possible tests, the best test is chosen to be the candidate
// A TestSuite structure stores all the candidate results, after a Candidate is stored in a TestSuite, all the tests
// and Candidate strucuture should be freed
#ifndef AETG_H
#define AETG_H

#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
#include <list>
#include "PairingFunction.h"
#include "Order.h"
#include "Test.h"

// Decrease these constants for BETTER runtime
//#define NUM_TIMES_TO_SHUFFLE_INITIAL_ORDER 20 // This is the max number of times an order will be shuffled in the constructor
//#define NUM_TEST_PER_CANDIDATE 50 // 1 means the first test generated is put into the test suite
#define NUM_TESTSUITE_PER_RESULT 200 // 1 means the first test suite is considered the result

#define PRINT_ENCODE_OFF
#define PRINT_COLLISION_STATEMENT_OFF

#ifdef DELETE_THIS
/*
 * For any given number of factors it generates an ordering.
 * Example ordering on 4 factors: 3, 2, 4, 1
 * So the third factor would be chosen first, the second factor would be chosen second, the fourth factor would be chosen third and the first factor would be chosen last.
 */
class Order {
public:
  int size; // The number of factors and the size of the orderArray
  std::vector<int> orderArray; // Stores a randomized order of consequtive numbers
  Order (int numFactors); // Initializes the vector and automatically scrambles
  void rescramble (); // scramble the orderArray
  void print(); // print the orderArray
};

/**
 * Initializes the orderArray and scrambles the array
 * The lowest number is 0 the highest numbers is numFactors - 1 
 * @param the max number of factors
 */
Order::Order (int numFactors) {
  size = numFactors; // save the number of factors in the structure
  std::vector<int>::iterator it; // use the iterator to initialize the vector
  for (int i=0; i<numFactors; i++) {
    orderArray.push_back (i); // initialize the vector to 1-numFactors in order
  }

  srand((unsigned)time(0)); // generate random number seed
  int random_integer = rand() % NUM_TIMES_TO_SHUFFLE_INITIAL_ORDER + 1; // generate random number
  for (int i=0; i< random_integer; i++) { // shuffle the ordering this many times, each time the program runs it should be shuffled a different amount of times
    std::random_shuffle(orderArray.begin(), orderArray.end()); // scramble the initial vector, this way each time the program is run it will start off with a different ordering
  }
}

/**
 * Scrambles the orderArray using random_shuffle()
 * http://www.cplusplus.com/reference/algorithm/random_shuffle/
 * This is O(n)
 */
void Order::rescramble () {
  std::random_shuffle(orderArray.begin(), orderArray.end());
}

/**
 * Print the orderArray
 */
void Order::print () {
  std::cout <<"Order: ";
  for (int i=0; i<size; i++) {
    std::cout << orderArray[i] << " ";
  }
  std::cout << std::endl;
}

/*
 * Test holds a set of 4 numbers, each number from a different factor
 */
class Test {
public:
  std::vector<int> testArray; // the vector that contains the four numbers
  int size; // The size of testArray (the same as the number of factors)
  int newPairs; // The number of new pairs that this test generates
  Test (int numFactors); // Initializes the elements of the testArray to -1
  void print (); // Prints out the testArray
  int test_Factor_Value (int factor, int value, int *hashTable); // tests a value and sees how many new pairs it would generate and returns that number
  void set_Factor_Value (int factor, int value, int *hashTable); // stores a factor's value into the Test, the factor is the array index, and the value input is its value
  void clear ();
};

Test::Test(int numFactors) {
  size = numFactors;
  newPairs = 0; // this variable starts at 0 and is incremented whenever a new value is stored in the Test using set_Factor_Value
  std::vector<int>::iterator it;
  for (int i=0; i<numFactors; i++) {
    testArray.push_back (-1); // initialize each item in the testArray to -1
  }
}

void Test::clear() {
  //  std::cout <<"Clearing Test" << std::endl;
  newPairs = 0;
  for (int i=0; i<size; i++) {
    testArray[i] = -1;
  }
}

void Test::print () {
  std::cout <<"Test Generated: ";
  for (int i=0; i<size; i++) {
    std::cout << testArray[i] << " ";
  }
  std::cout << std::endl;
}

// Do NOT change the test array OR hashTable in this function
// Main will have to save the max number of pairs, it's factor, and it's value
// Then when the selection for that factor is made, main will call set_Factor_Value
int Test::test_Factor_Value (int factor, int value, int *hashTable) {
  if (factor > size) return 0;

  int numOfNewPairs = 0;
  for (int i=0; i<size; i++) {
    if (testArray[i] == -1 || i == factor) continue;
    else {
      // Else see if the pair value and testArray[i] are a new pair
      // If they are a new pair, then increment number of pairs
      // if (hash(value, testArray[i]) == true) numOfPairs++;
      uint32_t hashA;
      uint32_t hashB;
      if (value > testArray[i]) {
	hashA = testArray[i];
	hashB = value;
      }
      else {
	hashA = value;
	hashB = testArray[i];
      }

      uint64_t hashResult = encode ((uint32_t)hashA, (uint32_t)hashB);
#ifdef PRINT_ENCODE_ON
      std::cout << "H(" << value << ", " << testArray[i] << ") = " << hashResult << std::endl;
#endif
      if (hashTable[hashResult] == 0) {
	//	std::cout << "Pair found on " << value << ", " << testArray[i] << std::endl;
	numOfNewPairs++;
      }
    }
  }

  return numOfNewPairs;
}

void Test::set_Factor_Value (int factor, int value, int *hashTable) {
  if (factor > size) return;
  testArray[factor] = value; // add the value to its corresponding factor in the testArray
  // traverse the test array
  for (int i=0; i<size; i++) { // now update the hashTable and increment the newPairs counter
    if (testArray[i] == -1 || i == factor) continue; // if the value of the index is -1, it hasn't been set yet
    else {

      uint32_t hashA;
      uint32_t hashB;
      if (value > testArray[i]) {
	hashA = testArray[i];
	hashB = value;
      }
      else {
	hashA = value;
	hashB = testArray[i];
      }

      uint64_t hashResult = encode ((uint32_t)hashA, (uint32_t)hashB); // compute the hash value
      //      std::cout << "Hash Result " << hashResult << std::endl;
      if (hashTable[hashResult] == 0) { 
	hashTable[hashResult] = 1; // if the value of the corresponding hashResult in the hashTable is 0, then it is a new pair
#ifdef PRINT_ENCODE_ON
	std::cout << "New Pair detected on pair (" << value << ", " << testArray[i] << ") = ";
	std::cout << "H(" << value << ", " << testArray[i] << ") = " << hashResult << std::endl;
#endif
	newPairs++; // so increment the newPairs counter
      }
      else {
#ifdef PRINT_COLLISION_STATEMENT_ON
	std::cout << "Collision detected on pair (" << value << ", " << testArray[i] << ") = " << hashResult << std::endl;
#endif
      }
    }
  }
}

class Candidate {
public:
  int counter_Candidate; // the number of tests generated
  Test *testArray; // memory is allocated in the constructor, this array is a FIXED size to NUM_TEST_PER_CANDIDATE
  int bestTestNewPairs; // The number of pairs in the bestTestSuite
  Candidate();
  ~Candidate();
  void inputTest(Test testToSave); // Takes in a test and the number of new pairs it would have
  Test chooseTest(int *hashArray);
  void clear ();
};

Candidate::Candidate () {
  counter_Candidate = 0;
  testArray = (Test *) calloc (NUM_TEST_PER_CANDIDATE, sizeof(Test));
  bestTestNewPairs = -1;
}

Candidate::~Candidate () {
  free (testArray);
}

void Candidate::clear () {
  counter_Candidate = 0;
  memset (testArray, 0, NUM_TEST_PER_CANDIDATE * sizeof(Test));
  bestTestNewPairs = -1;
}

void Candidate::inputTest (Test testToSave) {
  // The number of new pairs is the same as the current highest number of new pairs, so add this test to the array
  if (testToSave.newPairs == bestTestNewPairs) {
    testArray[counter_Candidate++] = testToSave;
  }
  if (testToSave.newPairs > bestTestNewPairs) {
    bestTestNewPairs = testToSave.newPairs;
    counter_Candidate = 0;
    testArray[counter_Candidate++] = testToSave;
  }
}

// Chooses a test, updates the hash table
// Returns the best Test, randomly chooses if there is more than one best test
Test Candidate::chooseTest(int *hashArray) {
  srand((unsigned)time(0));
  int choiceIndex = rand() % counter_Candidate;

  testArray[choiceIndex].newPairs = 0;
  for (int n=0; n<testArray[choiceIndex].size; n++) {
    testArray[choiceIndex].set_Factor_Value (n, testArray[choiceIndex].testArray[n], hashArray);
  }

  return testArray[choiceIndex];
}


// When size_testArray reaches NUM_TEST_PER_CANDIDATE then you pick the best test to put in the test suite
// When you input a testArray[bestTest] then you have to FREE the testArray (and at each index free the Test itself)
// Constructor:
// initialize counter_testSuite to 0
class TestSuite {
public:
  // Linked list of Tests
  std::list<Test> tests;
  TestSuite();
  ~TestSuite();
  void addTest (Test testToAdd);
  void clear();
  void print();
  int getSize();
};

TestSuite::TestSuite() {
}

void TestSuite::addTest(Test testToAdd) {
  tests.push_back(testToAdd);
}

void TestSuite::clear() {
  tests.clear();
}

int TestSuite::getSize() {
  return tests.size();
}

void TestSuite::print() {
  std::cout << "PRINTING TEST SUITE (" << tests.size() << ")" << std::endl;

  for (std::list<Test>::iterator it = tests.begin(); it != tests.end(); it++) {
    it->print();
  }

  std::cout << std::endl;
}
#endif
class AETG {
  int counter_Result; // The number of test suites generated

  // Linked list of TestSuite's
  int bestTestSuiteIndex; // The index containing the best test suite
  int bestTestSuiteSize; // The size of the best test suite
  AETG();
  ~AETG();
};

#endif
